import datastructure.linklist.ListNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/11 10:03
 * @description:
 */
public class Solution82 {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 虚拟头节点，避免头节点被删除时的处理麻烦
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy; // pre指向「当前不重复序列的最后一个节点」

        while (pre.next != null) {
            ListNode current = pre.next; // 当前待检查的节点
            // 1. 检查current是否有重复（current.next是否存在且值相等）
            if (current.next != null && current.val == current.next.val) {
                // 2. 记录重复值，跳过所有相同的节点
                int duplicateVal = current.val;
                while (current != null && current.val == duplicateVal) {
                    current = current.next; // 移动到重复序列的下一个节点
                }
                // 3. 连接pre和非重复节点（删除所有重复节点）
                pre.next = current;
            } else {
                // 无重复，pre正常后移
                pre = pre.next;
            }
        }
        // 返回虚拟头节点的next（正确的新头节点）
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.arrayToList(new int[]{1, 2, 3, 3, 4, 4, 5});
        Solution82 solution = new Solution82();
        ListNode newHead = solution.deleteDuplicates(head);
        ListNode.printList(newHead);
    }
}
